/************************************************************************
*																		*
*	Program:	UniversalTM.cpp											*
*																		*
*	Author:		Robb T. Koether											*
*																		*
*	Date:		Nov 16, 2005											*
*																		*
*	Purpose:	This program will read a description of a Turing 		*
*				Machine and then simulate that Turing Machine on input	*
*																		*
************************************************************************/

//	Include Header files

#include <iostream>
#include <string>
#include <cassert>
#include <fstream>
#include <iomanip.h>
#include "arraylist.h"

using namespace std;

const char EOT = '>';				// End-of-tape marker
const int runtimeLimit = 1000;		// Maximum number of transitions allowed

/************************************************************************
*																		*
*	The definition of the Transition class								*
*																		*
************************************************************************/

class Transition
{
//	Private data members

	private:
		int srcState;
		char tapeSym;
		int dstState;
		char action;

//	Public member functions

	public:
	
	//	Constructors
	
		Transition() : srcState(0), tapeSym('_'), dstState(0), action('_') {}
		Transition(int src, char tsym, int dst, char act) :
			srcState(src), tapeSym(tsym), dstState(dst), action(act) {}
	
	//	Inspectors
	
		int Src() const {return srcState;}
		char TapeSym() const {return tapeSym;}
		int Dst() const {return dstState;}
		char Action() const {return action;}
	
	//	Facilitators
	
		void input(istream& in);
		void output(ostream& out) const;
};

/************************************************************************
*																		*
*	Function:	input													*
*																		*
************************************************************************/

void Transition::input(istream& in)
{
//	Read left parenthesis

	char c;
	in >> c;
	if (c != '(')
	{
		cerr << "Error: Left parenthesis missing at beginning of transition" << endl;
		exit(1);
	}

//	Read source state and comma

	in >> srcState;
	in >> c;
	if (c != ',')
	{
		cerr << "Error: Comma missing after source state" << endl;
		exit(1);
	}

//	Read tape symbol and semicolon

	in >> tapeSym;
	in >> c;
	if (c != ';')
	{
		cerr << "Error: Semicolon missing before destination state" << endl;
		exit(1);
	}

//	Read destination state and comma

	in >> dstState;
	in >> c;
	if (c != ',')
	{
		cerr << "Error: Comma missing after destination state" << endl;
		exit(1);
	}

//	Read action and right parethesis

	in >> action;
	in >> c;
	if (c != ')')
	{
		cerr << "Error: Right parenthesis missing after transition" << endl;
		exit(1);
	}
	return;
}

/************************************************************************
*																		*
*	Function:	output													*
*																		*
************************************************************************/

void Transition::output(ostream& out) const
{
	out << '(' << srcState << ", " << tapeSym
		<< "; " << dstState << ", " << action << ')';
	return;
}

/************************************************************************
*																		*
*	Function:	operator>>												*
*																		*
************************************************************************/

istream& operator>>(istream& in, Transition& t);

istream& operator>>(istream& in, Transition& t)
{
	t.input(in);
	return in;
}

/************************************************************************
*																		*
*	Function:	operator<<												*
*																		*
************************************************************************/

ostream& operator<<(ostream& out, const Transition& t);

ostream& operator<<(ostream& out, const Transition& t)
{
	t.output(out);
	return out;
}

//	Function prototypes

int findTransition(int currState, char tapeSymbol, ArrayList<Transition>& delta);
void displayGoodTransition(int i, ArrayList<Transition>& delta);
void displayBadTransition(int currState, char tapeSymbol);

/************************************************************************
*																		*
*	Function:	main													*
*																		*
************************************************************************/

int main()
{
	int count = 0;
	
	ArrayList<char> alphabet;
	ArrayList<Transition> delta;
	ArrayList<int> halt;
	ArrayList<char> tape(1);
	tape[1] = EOT;			// Write EOT at left end of tape
	
//	Read the Turing Machine from a file

	cout << "Enter the TM file name: ";
	string fileName;
	cin >> fileName;
	fstream fin(fileName.c_str());
	if (!fin)
	{
		cerr << "Failed to open " << fileName << endl;
		exit(1);
	}
	fin >> alphabet;	// Read the tape alphabet
	fin >> delta;		// Read the transition function
	fin >> halt;		// Read the halting states

//	Expand '?' symbols

	for (int i = 1; i <= delta.Size(); i++)
	{
		if (delta[i].TapeSym() == '?')
		{
			for (int j = 1; j <= alphabet.Size(); j++)
			{
				int pos = findTransition(delta[i].Src(), alphabet[j], delta);
				if (pos == -1)
				{
					if (delta[i].Action() == '?')
						delta.PushBack(Transition(delta[i].Src(), alphabet[j], delta[i].Dst(), alphabet[j]));
					else
						delta.PushBack(Transition(delta[i].Src(), alphabet[j], delta[i].Dst(), delta[i].Action()));
				}
			}
			delta.Delete(i);
			i--;
		}
	}

//	Put the input onto the tape

	int currState = 0;
	int currPos = 2;
	char tapeSymbol;
	bool rejected = false;
	
	cout << "Enter the input string: ";
	string input;
	cin >> input;
	for (int i = 0; i < input.size(); i++)
		tape.PushBack(input[i]);
	tape.PushBack('_');
		
	cout << endl << "Tape input" << endl;
	for (int i = 1; i <= tape.Size(); i++)
		cout << tape[i];
	cout << endl;
	cout << " ^" << endl;

//	Continue with transitions until (1) an error, (2) a halt state, or
//	(3) max number of transitions

	while (!rejected && halt.Search(currState) == 0 && count < runtimeLimit)
	{
	//	Get the current tape symbol
	
		tapeSymbol = tape[currPos];

	//	Find an appropriate transition
	
		int trans = findTransition(currState, tapeSymbol, delta);
		if (trans == -1)
		{
			displayBadTransition(currState, tapeSymbol);
			rejected = true;
		}
		else
			displayGoodTransition(trans, delta);
		
	//	Carry out the action
	
		if (!rejected)
		{
		//	Change state and move left or right or write symbol
		
			currState = delta[trans].Dst();
			if (delta[trans].Action() == 'L')
				currPos--;
			else if (delta[trans].Action() == 'R')
			{
				if (tape.Size() <= currPos)
					tape.PushBack('_');		// Show the next blank
				currPos++;
			}
			else
				tape[currPos] = delta[trans].Action();
				
		//	Display the tape
		
			int length;
			for (length = tape.Size(); length > currPos && tape[length] == '_'; length--)
				continue;
		
			cout << "tape = ";	
			for (int i = 1; i < currPos; i++)
				cout << ' ' << tape[i];
			cout << '@';
			for (int i = currPos; i <= length; i++)
				cout << tape[i] << ' ';
			cout << '_' << endl;
		}
		count++;
	}
	
	if (count >= runtimeLimit)
		cout << endl << "Program timed out after " << runtimeLimit << " transitions" << endl;
	
	cout << endl << "Tape output" << endl;
	
	int i;
	for (i = tape.Size(); i > 0 && tape[i] == '_'; i--)
		continue;
	int length = i;
	
	for (int i = 1; i <= length; i++)
		cout << tape[i];
	cout << '_' << endl;
	for (int i = 1; i < currPos; i++)
		cout << ' ';
	cout << '^' << endl;
	
	return 0;
}

/************************************************************************
*																		*
*	Function:	findTransition											*
*																		*
************************************************************************/

int findTransition(int currState, char tapeSymbol, ArrayList<Transition>& delta)
{
	for (int i = 1; i <= delta.Size(); i++)
		if (delta[i].Src() == currState && delta[i].TapeSym() == tapeSymbol)
			return i;
			
	return -1;
}

/************************************************************************
*																		*
*	Function:	displayGoodTransition									*
*																		*
************************************************************************/

void displayGoodTransition(int i, ArrayList<Transition>& delta)
{
	cout << "State " << setw(2) << delta[i].Src()
		 << "; read " << delta[i].TapeSym()
		 << " -> state " << setw(2) << delta[i].Dst();
	if (delta[i].Action() == 'L')
		cout << "; move L;  ";
	else if (delta[i].Action() == 'R')
		cout << "; move R;  ";
	else
		cout << "; write " << delta[i].Action() << "; ";
	return;
}

/************************************************************************
*																		*
*	Function:	displayBadTransition									*
*																		*
************************************************************************/

void displayBadTransition(int currState, char tapeSymbol)
{
	cout << "State " << setw(2) << currState 
		 <<"; read " << tapeSymbol <<  " -> the implicit reject state" << endl;
	return;
}